{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 量子相位估计算法\n",
    "\n",
    "\n",
    "`Linux` `CPU` `全流程` `初级` `中级` `高级`\n",
    "\n",
    "[![](https://gitee.com/mindspore/docs/raw/master/resource/_static/logo_source.png)](https://gitee.com/mindspore/mindquantum/blob/master/tutorials/4.quantum_phase_estimation.ipynb) [![](https://gitee.com/mindspore/mindquantum/raw/master/tutorials/images/view_mindquantum_api.png)](https://mindspore.cn/mindquantum/api/zh-CN/master/index.html)\n",
    "\n",
    "## 概述\n",
    "\n",
    "量子相位估计算法(Quantum hase Estimation Algorithm，简称QPE)，是很多量子算法的关键。假设一个幺正算符 $U$，这个幺正算符作用在其本征态 $|u\\rangle$ 上会出现一个相位 $e^{2\\pi i \\varphi}$，现在我们假设 $U$ 算符的本征值未知，也就是 $\\varphi$ 未知，但是 $U$ 算符和本征态 $|u\\rangle$ 已知，相位估计算法的作用就是对这个相位 $\\varphi$ 进行估计。  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![QPE](./images/quantum_phase_estimation.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 算法解析\n",
    "\n",
    "相位估计算法的实现需要两个寄存器(register)，第一个寄存器包含t个初始在的 $|0\\rangle$ 的量子比特，比特数和最后相位估计的结果的精度和算法的成功概率相关；第二个寄存器初始化在幺正算符 $U$ 的而本征态 $|u\\rangle$ 上。相位估计算法主要分为三步：\n",
    "\n",
    "1. 对第一个寄存器的所有量子比特进行``Hadamard``门操作，对第二寄存器连续进行``控制U``门操作，其中U门的幂次依次为 $2^0, 2^1,...,2^{t-1}$，控制比特依次为 $q_{t-1}, q_{t-2},..., q_{1}, q_{0}$。这时第一寄存器中的态就会变为\n",
    "\n",
    "$$\n",
    "|\\psi_1\\rangle=\\frac{1}{2^{t/2}}\\left(|0\\rangle+e^{i2\\pi 2^{t-1}\\varphi}|1\\rangle\\right)\\left(|0\\rangle+e^{i2\\pi2^{t-2}\\varphi}|1\\rangle\\right)...\\left(|0\\rangle+e^{i2\\pi 2^{0}\\varphi}|1\\rangle\\right) = \\frac{1}{2^{t/2}}\\sum_{k=0}^{2^t-1}e^{i2\\pi\\varphi k}|k\\rangle\n",
    "$$\n",
    "\n",
    "其中k为直积态的十进制表示，比如 $k=0$ 表示第一寄存器中t个比特全部在基态 $|00...00\\rangle$,  $k=2$ 表示 $|00...10\\rangle$，以此类推。\n",
    "\n",
    "2. 对第一寄存器的进行量子傅里叶变换的逆变换(Inverse Quantum Fourier Transform)，在线路中表示成 $QFT^\\dagger$, 对 $|\\psi_1\\rangle$ 进行逆量子傅里叶变换可得 $|\\psi_2\\rangle$\n",
    "\n",
    "$$\n",
    "|\\psi_2\\rangle=QFT^\\dagger|\\psi_1\\rangle =\\frac{1}{2^t}\\sum_{x=0}^{2^t-1}a_x|x\\rangle\n",
    "$$\n",
    "其中\n",
    "$$\n",
    "a_x=\\sum_{k=0}^{2^t-1}e^{2\\pi i k(\\varphi-x/2^t)}\n",
    "$$\n",
    "为本征基矢 $|x\\rangle$ ($x=0.1,...,2^t$) 对应的概率幅 。由上式可得，当 $2^t\\varphi$ 为整数，且满足 $x=2^t\\varphi$ 时，概率幅取最大值1，此时第一寄存器的末态可以精确反映 $\\varphi$；当 $2^t\\varphi$ 不是整数时，$x$ 为 $\\varphi$ 的估计，且t越大，估计精度越高。\n",
    "\n",
    "3. 对第一寄存器的量子比特进行测量，得到第一寄存器的末态 $f=\\sum_{x}^{2^t-1}a_x|x\\rangle$, $x=0,1,...,2^t$；从中找到最大的概率幅 $a_{max}$，其对应的本征基矢 $|x\\rangle$ 中的 $x$ 在除以 $2^t$ 即为相位的估计值。\n",
    "\n",
    "\n",
    "\n",
    "## QPE代码实现\n",
    "\n",
    "下面用一个实例来演示如何在mindquantum实现相位估计算法，选择 ``T``门作为进行估计的幺正算符，由定义\n",
    "\n",
    "$$\n",
    "T|1\\rangle=e^{i\\pi/4}|1\\rangle\n",
    "$$\n",
    "可知需要估计的相位角为 $\\varphi=\\frac{1}{8}$。\n",
    "\n",
    "首先导入相关依赖"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mindquantum import Circuit\n",
    "from mindquantum import Simulator\n",
    "from mindquantum import UN, PhaseShift, qft, H, X, BARRIER\n",
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "``Mindquantum.UN`` 可以指定量子门，目标比特和控制比特，从而在线路中搭建门操作。因为我们已知 $\\varphi=1/8$，当 $t=3$ 时可令 $2^t\\varphi$ 为整数，所以第一寄存器只需要3个比特即可准确估计；又已知 ``T`` 门的本征态为 $|1\\rangle$，所以第二寄存器选择一个比特，即：我们需要搭建4比特线路，前 $q_0, q_1, q_2$ 比特用于估计，属于第一寄存器；$q_3$ 属于第二寄存器用于传入 $T$ 算符的本征态。\n",
    "\n",
    "利用 ``UN`` 对 $q_0, q_1, q_2$ 进行 ``Hadamard`` 门操作， 用 ``X`` 门对 $q_3$ 进行翻转，得到 ``T`` 门的本征态 $|1\\rangle$。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\"></pre>\n"
      ],
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"white-space: pre;\"><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q0: ──H──</span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">         </span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q1: ──H──</span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">         </span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q2: ──H──</span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">         </span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q3: ──X──</span>\n",
       "</pre>\n"
      ],
      "text/plain": [
       "q0: ──H──\n",
       "         \n",
       "q1: ──H──\n",
       "         \n",
       "q2: ──H──\n",
       "         \n",
       "q3: ──X──"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "n = 3\n",
    "c = Circuit()\n",
    "c += UN(H, n)\n",
    "c += X.on(n)\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "以 $q_3$ 为目标比特，添加 ``控制PhaseShift``门"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\"></pre>\n"
      ],
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"white-space: pre;\"><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q0: ──H────────────────────────────────●──────</span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                                       │      </span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q1: ──H───────────────────●────────────┼──────</span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                          │            │      </span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q2: ──H───────●───────────┼────────────┼──────</span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">              │           │            │      </span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q3: ──X────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">PS</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(phi)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">PS</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(</span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">2</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">*phi)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">PS</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(</span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">4</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">*phi)──</span>\n",
       "</pre>\n"
      ],
      "text/plain": [
       "q0: ──H────────────────────────────────●──────\n",
       "                                       │      \n",
       "q1: ──H───────────────────●────────────┼──────\n",
       "                          │            │      \n",
       "q2: ──H───────●───────────┼────────────┼──────\n",
       "              │           │            │      \n",
       "q3: ──X────PS(phi)────PS(2*phi)────PS(4*phi)──"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "for i in range(n):\n",
    "    c += PhaseShift({'phi': 2**i}).on(n, n-i-1)\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对第一寄存器比特进行逆傅里叶变换"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\"></pre>\n"
      ],
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"white-space: pre;\"><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q0: ──H────────────────────────────────●────────@──────────────────────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">PS</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(-π/</span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">4</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">PS</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(-π/</span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">2</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">)────H──</span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                                       │        │                             │           │           </span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q1: ──H───────────────────●────────────┼────────┼─────────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">PS</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(-π/</span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">2</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">)────H───────┼───────────●───────────</span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">                          │            │        │            │                │                       </span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q2: ──H───────●───────────┼────────────┼────────@────H───────●────────────────●───────────────────────</span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">              │           │            │                                                              </span>\n",
       "<span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">q3: ──X────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">PS</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(phi)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">PS</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(</span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">2</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">*phi)────</span><span style=\"color: #800080; text-decoration-color: #800080; font-weight: bold\">PS</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">(</span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">4</span><span style=\"color: #000080; text-decoration-color: #000080; font-weight: bold\">*phi)──────────────────────────────────────────────────────────</span>\n",
       "</pre>\n"
      ],
      "text/plain": [
       "q0: ──H────────────────────────────────●────────@──────────────────────────PS(-π/4)────PS(-π/2)────H──\n",
       "                                       │        │                             │           │           \n",
       "q1: ──H───────────────────●────────────┼────────┼─────────PS(-π/2)────H───────┼───────────●───────────\n",
       "                          │            │        │            │                │                       \n",
       "q2: ──H───────●───────────┼────────────┼────────@────H───────●────────────────●───────────────────────\n",
       "              │           │            │                                                              \n",
       "q3: ──X────PS(phi)────PS(2*phi)────PS(4*phi)──────────────────────────────────────────────────────────"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c += BARRIER\n",
    "c += qft(range(n)).hermitian()\n",
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "选择后端、传入总比特数创建模拟器，将 $\\varphi$ 值传入并进行演化，得到末态"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1¦1100⟩\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"white-space:pre;overflow-x:auto;line-height:normal;font-family:Menlo,'DejaVu Sans Mono',consolas,'Courier New',monospace\"></pre>\n"
      ],
      "text/plain": []
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"white-space: pre;\"><span style=\"color: #808000; text-decoration-color: #808000\">shots: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">100</span>\n",
       "<span style=\"color: #808000; text-decoration-color: #808000\">Keys: q3 q2 q1 q0│</span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.00</span><span style=\"color: #808000; text-decoration-color: #808000\">     </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.2</span><span style=\"color: #808000; text-decoration-color: #808000\">         </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.4</span><span style=\"color: #808000; text-decoration-color: #808000\">         </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.6</span><span style=\"color: #808000; text-decoration-color: #808000\">         </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">0.8</span><span style=\"color: #808000; text-decoration-color: #808000\">         </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">1.0</span>\n",
       "<span style=\"color: #808000; text-decoration-color: #808000\">─────────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴</span>\n",
       "<span style=\"color: #808000; text-decoration-color: #808000\">             </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">1100</span><span style=\"color: #808000; text-decoration-color: #808000\">│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓</span>\n",
       "<span style=\"color: #808000; text-decoration-color: #808000\">                 │                                                            </span>\n",
       "<span style=\"color: #808000; text-decoration-color: #808000; font-weight: bold\">{</span><span style=\"color: #008000; text-decoration-color: #008000\">'1100'</span><span style=\"color: #808000; text-decoration-color: #808000\">: </span><span style=\"color: #008080; text-decoration-color: #008080; font-weight: bold\">100</span><span style=\"color: #808000; text-decoration-color: #808000; font-weight: bold\">}</span>\n",
       "</pre>\n"
      ],
      "text/plain": [
       "shots: 100\n",
       "Keys: q3 q2 q1 q0│0.00     0.2         0.4         0.6         0.8         1.0\n",
       "─────────────────┼───────────┴───────────┴───────────┴───────────┴───────────┴\n",
       "             1100│▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓\n",
       "                 │                                                            \n",
       "{'1100': 100}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from mindquantum import Measure\n",
    "sim = Simulator('projectq', c.n_qubits)\n",
    "phi = 0.125\n",
    "sim.apply_circuit(c,{'phi': 2*np.pi*phi})\n",
    "qs = sim.get_qs()\n",
    "print(sim.get_qs(ket=True))\n",
    "res = sim.sampling(UN(Measure(), c.n_qubits), shots=100)\n",
    "res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "找出概率幅最大值的位置"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "12\n"
     ]
    }
   ],
   "source": [
    "index = np.argmax(np.abs(qs))\n",
    "print(index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意此时的 ``index`` 对应的 $x$ 并不是真正的估计值，被 $2^t$ 除之后也不是，因为测量结果中包括第二寄存器中的辅助比特，需要将``index``转成二进制后将辅助位剔除"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100\n"
     ]
    }
   ],
   "source": [
    "bit_string = bin(index)[2:].zfill(c.n_qubits)[1:]\n",
    "print(bit_string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在将二进制转回十进制，得到我们最终的估计值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.125"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "theta_exp = int(bit_string[::-1], 2) / 2**n\n",
    "theta_exp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "可见得到的估计相位和 $\\varphi$ 近似相等。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 参考文献\n",
    "\n",
    "[1] Michael A. Nielsen and Isaac L. Chuang. [Quantum computation and quantum information](www.cambridge.org/9781107002173)"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "6cd6e2203b621035efd3b4ac9716079b52ce7fc5622f6651a3ae71459e0d54ce"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
